using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo.FenCi
{
    public class FenCiBMM : IFenCiProvider
    {
        private CiTrieNode root = new CiTrieNode('\0');
        public void AddCi(params string[] cis)
        {
            foreach (string ci in cis)
            {
                CiTrieNode node = root;
                for (int i = ci.Length - 1; i >= 0; i-- )
                {
                    char c = ci[i];
                    CiTrieNode node2;
                    if (!node.TryGetValue(c, out node2))
                    {
                        node2 = new CiTrieNode(c);
                        node.Add(node2);
                    }
                    node = node2;
                }
                node.IsMatch = true;
            }
        }
        public string[] FenCi(string text)
        {
            List<string> ret = new List<string>();
            int i = text.Length-1, i0 = i;
            while(i>=0)
            {
                int i1 = i;
                CiTrieNode node = root;
                for(int j = i; j>=0;)
                {
                    CiTrieNode node2;
                    if(!node.TryGetValue(text[j], out node2))
                    {
                        break;
                    }
                    node = node2;
                    j--;
                    if(node.IsMatch)
                    {
                        i1 = j;
                    }
                }
                if(i1!=i)
                {
                    if(i0!=i)
                    {
                        ret.Add(text.Substring(i+1, i0-i));
                        i0 = i1;
                    }
                    ret.Add(text.Substring(i1+1,i-i1));
                    i = i1;
                    i0 = i1;
                }
                else
                {
                    i--;
                }
            }
            if(i0!=i)
            {
                ret.Add(text.Substring(0,i0+1));
            }
            ret.Reverse();
            return ret.ToArray();
        }
    }
}
